Greatest Common Divisor (GCD) is one of the basic subjects in computational number theory. It has a wide application in encryption and analysis of cryptography. For inputing B and C, an algorithm based on right-shift k-ary reduction proposed by Sorenson was presented for finding the integers x and y which satisfy the least significant bits of Bx-Cy were 0,i.e., Bx-Cy=0(mod2e) where positive integer e was a constant. It could do a lot of right shifts and reduce a large number of cycles with taking advantage of the algorithm for finding the integers x and y. A fast GCD algorithm was proposed combined with modulus algorithm. When the size of the input was n bits, the worst complexity of the fast GCD algorithm was still O(n2).In the best case, the complexity of the proposed algorithm could achieve O(nlog2 nlog logn). The experimental data show that actual implementations given input about more than 200000 bits, the fast GCD algorithm is faster than the Binary GCD algorithm, and the fast GCD algorithm is twice as fast as the Binary GCD algorithm for 1 million bits of input.
This paper analysed the functions of all parts of the USB transfer subsystem in real-time human motion capture device, and introduced its detailed designing methods of this subsystem. The USB transfer subsystem can transfer exact data in real time while the device is running and collecting human motion data.